{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2023 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# ranking_sample_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/sat/ranking_sample_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/ortools/sat/samples/ranking_sample_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Code sample to demonstrates how to rank intervals.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "def RankTasks(model, starts, presences, ranks):\n",
    "    \"\"\"This method adds constraints and variables to links tasks and ranks.\n",
    "\n",
    "    This method assumes that all starts are disjoint, meaning that all tasks have\n",
    "    a strictly positive duration, and they appear in the same NoOverlap\n",
    "    constraint.\n",
    "\n",
    "    Args:\n",
    "      model: The CpModel to add the constraints to.\n",
    "      starts: The array of starts variables of all tasks.\n",
    "      presences: The array of presence variables of all tasks.\n",
    "      ranks: The array of rank variables of all tasks.\n",
    "    \"\"\"\n",
    "\n",
    "    num_tasks = len(starts)\n",
    "    all_tasks = range(num_tasks)\n",
    "\n",
    "    # Creates precedence variables between pairs of intervals.\n",
    "    precedences = {}\n",
    "    for i in all_tasks:\n",
    "        for j in all_tasks:\n",
    "            if i == j:\n",
    "                precedences[(i, j)] = presences[i]\n",
    "            else:\n",
    "                prec = model.NewBoolVar(f\"{i} before {j}\")\n",
    "                precedences[(i, j)] = prec\n",
    "                model.Add(starts[i] < starts[j]).OnlyEnforceIf(prec)\n",
    "\n",
    "    # Treats optional intervals.\n",
    "    for i in range(num_tasks - 1):\n",
    "        for j in range(i + 1, num_tasks):\n",
    "            tmp_array = [precedences[(i, j)], precedences[(j, i)]]\n",
    "            if not cp_model.ObjectIsATrueLiteral(presences[i]):\n",
    "                tmp_array.append(presences[i].Not())\n",
    "                # Makes sure that if i is not performed, all precedences are false.\n",
    "                model.AddImplication(presences[i].Not(), precedences[(i, j)].Not())\n",
    "                model.AddImplication(presences[i].Not(), precedences[(j, i)].Not())\n",
    "            if not cp_model.ObjectIsATrueLiteral(presences[j]):\n",
    "                tmp_array.append(presences[j].Not())\n",
    "                # Makes sure that if j is not performed, all precedences are false.\n",
    "                model.AddImplication(presences[j].Not(), precedences[(i, j)].Not())\n",
    "                model.AddImplication(presences[j].Not(), precedences[(j, i)].Not())\n",
    "            # The following bool_or will enforce that for any two intervals:\n",
    "            #    i precedes j or j precedes i or at least one interval is not\n",
    "            #        performed.\n",
    "            model.AddBoolOr(tmp_array)\n",
    "            # Redundant constraint: it propagates early that at most one precedence\n",
    "            # is true.\n",
    "            model.AddImplication(precedences[(i, j)], precedences[(j, i)].Not())\n",
    "            model.AddImplication(precedences[(j, i)], precedences[(i, j)].Not())\n",
    "\n",
    "    # Links precedences and ranks.\n",
    "    for i in all_tasks:\n",
    "        model.Add(ranks[i] == sum(precedences[(j, i)] for j in all_tasks) - 1)\n",
    "\n",
    "\n",
    "def RankingSampleSat():\n",
    "    \"\"\"Ranks tasks in a NoOverlap constraint.\"\"\"\n",
    "\n",
    "    model = cp_model.CpModel()\n",
    "    horizon = 100\n",
    "    num_tasks = 4\n",
    "    all_tasks = range(num_tasks)\n",
    "\n",
    "    starts = []\n",
    "    ends = []\n",
    "    intervals = []\n",
    "    presences = []\n",
    "    ranks = []\n",
    "\n",
    "    # Creates intervals, half of them are optional.\n",
    "    for t in all_tasks:\n",
    "        start = model.NewIntVar(0, horizon, f\"start[{t}]\")\n",
    "        duration = t + 1\n",
    "        end = model.NewIntVar(0, horizon, f\"end[{t}]\")\n",
    "        if t < num_tasks // 2:\n",
    "            interval = model.NewIntervalVar(start, duration, end, f\"interval[{t}]\")\n",
    "            presence = True\n",
    "        else:\n",
    "            presence = model.NewBoolVar(f\"presence[{t}]\")\n",
    "            interval = model.NewOptionalIntervalVar(\n",
    "                start, duration, end, presence, f\"o_interval[{t}]\"\n",
    "            )\n",
    "        starts.append(start)\n",
    "        ends.append(end)\n",
    "        intervals.append(interval)\n",
    "        presences.append(presence)\n",
    "\n",
    "        # Ranks = -1 if and only if the tasks is not performed.\n",
    "        ranks.append(model.NewIntVar(-1, num_tasks - 1, f\"rank[{t}]\"))\n",
    "\n",
    "    # Adds NoOverlap constraint.\n",
    "    model.AddNoOverlap(intervals)\n",
    "\n",
    "    # Adds ranking constraint.\n",
    "    RankTasks(model, starts, presences, ranks)\n",
    "\n",
    "    # Adds a constraint on ranks.\n",
    "    model.Add(ranks[0] < ranks[1])\n",
    "\n",
    "    # Creates makespan variable.\n",
    "    makespan = model.NewIntVar(0, horizon, \"makespan\")\n",
    "    for t in all_tasks:\n",
    "        model.Add(ends[t] <= makespan).OnlyEnforceIf(presences[t])\n",
    "\n",
    "    # Minimizes makespan - fixed gain per tasks performed.\n",
    "    # As the fixed cost is less that the duration of the last interval,\n",
    "    # the solver will not perform the last interval.\n",
    "    model.Minimize(2 * makespan - 7 * sum(presences[t] for t in all_tasks))\n",
    "\n",
    "    # Solves the model model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    status = solver.Solve(model)\n",
    "\n",
    "    if status == cp_model.OPTIMAL:\n",
    "        # Prints out the makespan and the start times and ranks of all tasks.\n",
    "        print(f\"Optimal cost: {solver.ObjectiveValue()}\")\n",
    "        print(f\"Makespan: {solver.Value(makespan)}\")\n",
    "        for t in all_tasks:\n",
    "            if solver.Value(presences[t]):\n",
    "                print(\n",
    "                    f\"Task {t} starts at {solver.Value(starts[t])} \"\n",
    "                    f\"with rank {solver.Value(ranks[t])}\"\n",
    "                )\n",
    "            else:\n",
    "                print(\n",
    "                    f\"Task {t} in not performed \"\n",
    "                    f\"and ranked at {solver.Value(ranks[t])}\"\n",
    "                )\n",
    "    else:\n",
    "        print(f\"Solver exited with nonoptimal status: {status}\")\n",
    "\n",
    "\n",
    "RankingSampleSat()\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}
